<?php
/**
 * @title 64. 最小路径和 - 遍历
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function minPathSum($grid) {
        /**
         * @since 2020-07-23 宽高
         * @since 2020-07-23 极端情况排除
         */
        $h = count($grid);
        if($h == 0){
            return 0;
        } else {}
        $w = count($grid[0]);
        if($w == 0){
            return 0;
        } else {}

        /**
         * @since 2020-07-23 每个位置最优解
         */
        $dps = [];

        /**
         * @since 2020-07-23 遍历各个点
         */
        for ($i=0; $i<$h; $i++){
            for($j=0; $j<$w; $j++){
                /**
                 * @since 2020-07-23 2个上级点都存在
                 */
                if(isset($dps[$i-1][$j]) AND isset($dps[$i][$j-1])){
                    $dp = $grid[$i][$j] + min($dps[$i-1][$j], $dps[$i][$j-1]);
                } elseif(isset($dps[$i-1][$j])) {
                    /**
                     * @since 2020-07-23 只存在一个点
                     */
                    $dp = $grid[$i][$j] + $dps[$i-1][$j];
                } elseif(isset($dps[$i][$j-1])){
                    /**
                     * @since 2020-07-23 只存在一个点
                     */
                    $dp = $grid[$i][$j] + $dps[$i][$j-1];
                } else {
                    /**
                     * @since 2020-07-23 起点
                     */
                    $dp = $grid[$i][$j];
                }

                $dps[$i][$j] = $dp;
            }
        }

        /**
         * @return
         */
        return $dps[$h-1][$w-1];
        
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.23.php
 */
$datas = [
    [
        [1,3,1],
        [1,5,1],
        [4,2,1]
    ],
];

require_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->minPathSum($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
